package com.wyr.leetcode.step2.dp;

public class RobTestII {
    /**
     * 213. 打家劫舍 II
     * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。
     * 这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
     * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
     *
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
     *
     * https://leetcode.cn/problems/house-robber-ii/description/?envType=problem-list-v2&envId=array
     */
    public int rob(int[] nums) {
        if(nums==null||nums.length==0)
            return 0;
        if(nums.length ==1){
            return nums[0];
        }
        return Math.max(nums[0]+process(nums,2,nums.length-2), process(nums,1,nums.length-1));
    }

    public int rob2(int[] nums) {
        if(nums==null||nums.length==0)
            return 0;
        if(nums.length==1)
            return nums[0];
        int N=nums.length;
        // 0下标偷，偷的范围：[2,N-2]
        int [] dp1=new int[N+2];
        for(int i=N-2;i>=2;i--){
            dp1[i]=Math.max(nums[i]+dp1[i+2],dp1[i+1]);
        }
        // 0下标不偷，偷的范围：[1,N-1]
        int [] dp2=new int[N+2]; // dp[i]，从i下表开始偷
        for(int i=N-1;i>=1;i--){
            dp2[i]=Math.max(nums[i]+dp2[i+2],dp2[i+1]);
        }
        return Math.max(nums[0]+dp1[2], dp2[1]);
    }

    /**
     如果偷 nums[0]，那么 nums[1] 和 nums[n−1] 不能偷，
     问题变成从 nums[2] 到 nums[n−2] 的非环形版本。
     感觉绕了一个弯，不如直接求 nums[2] 到 nums[n−2]。
     如果不偷 nums[0]，那么问题变成从 nums[1] 到 nums[n−1] 的非环形版本。
     */

    public int process(int [] nums, int left ,int right){
        if(left>right)
            return 0;
        int p1=nums[left]+process(nums,left+2,right);
        //在index处选择不偷
        int p2=process(nums,left+1,right);
        return Math.max(p1,p2);
    }
}
